import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

// 力扣210. 课程表 II
class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adj = new ArrayList<>(); // 初始化邻接表
        for(int i = 0; i < numCourses; i++){
            adj.add(new ArrayList<>());
        }
        int[] inDegree = new int[numCourses]; // inDegree[i] 表示学习课程 i 之前需要先修的课程数量
        for (int[] edge : prerequisites) { // 构建邻接表和入度数组
            adj.get(edge[1]).add(edge[0]); // 在edge[1] 的 后面有哪些 edge[0]（就是有哪些edge[0]以edge[1]作为先修课程）
            inDegree[edge[0]]++;
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if(inDegree[i] == 0){ // inDegree[i] == 0 表示第i门课程没有先修要求，可以直接开始学习
                queue.offer(i);
            }
        }
        int[] result = new int[numCourses];
        int index = 0;
        while(!queue.isEmpty()){
            int u = queue.poll();
            result[index++] = u;
            for (int v : adj.get(u)) { // 当前v课程只有以u为先修课程就加入队列中
                if(--inDegree[v] == 0){ // 这段代码中的 --inDegree[v] 会永久修改 inDegree[v] 的值，且每次判断时都会执行修改。
                    queue.offer(v);
                }
            }
        }
        if (index != numCourses) { // 检查是否所以课程都被安排
            return new int[0];
        }
        return result;
    }
}